package homework;

public class HomeWork41 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeHelper(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
    }

    private TreeNode buildTreeHelper(int[] preorder, int s1, int end1 , int[] inorder, int s2, int end2) {
        if(s1==end1){
            return null;
        }
        int k=preorder[s1];
        TreeNode root=new TreeNode(k);
        int index=0;
        for (int i = s2; i <inorder.length ; i++) {
            if(inorder[i]==k){
                index=i;
            }
        }
        int left_num=index-s2;
        root.left=buildTreeHelper(preorder,s1+1,s1+left_num+1,inorder,s2,s2+left_num);
        root.right=buildTreeHelper(preorder,s1+left_num+1,end1,inorder,index+1,end2);
        return root;
    }
}
